// a b c d e f g
// a b e c d h f g

// c d e => 2 3 4
// e c d h => 4 2 3 0? 0表示之前不存在

//  通过上边的两个序列，可以求出来，最终这样的结果【0：c，1：d 】就可以保证某些元素不用移动

// 需要求联系性最强的 子序列

// 2 3 7 6 8 4 9 11 ==> 最长的个数 2 3 6 8 9 11 「6个」

// 看潜力值
//  2
//  2 3
//  2 3 7 先暂且认为这个序列够长
//  2 3 6 遇到了6 6的连续性更强 6替换了7
//  2 3 6 8
//  2 3 6 8
//  2 3 4 8 //遇到了4 通过二分查找快速找到比4 大的 6 替换掉 （4 替换 6） [记录8之前是6]
//  2 3 4 8 9
//  2 3 4 8 9 11

//  2 3 1 5 6 8 7 9 4  == >  2 3 5 6 7 9  6个

//  2      2前一个是null
//  2 3    3的前一个是2
//  1 3    1的前一个是null
//  1 3 5   5的前一个是3
//  1 3 5 6   6的前一个是5
//  1 3 5 6 8  8的前一个是6
//  1 3 5 6 7  7的前一个是6
//  1 3 5 6 7 9  9的前一个是7
//  1 3 4 6 7 9  4的前一个是3

// 9 7 6 5 3 2 追溯回去 ===》 2 3 5 6 7 9

// 实现最长递增子序列
function getSequence(arr) {
  const result = [0]; // 默认0开始
  const len = arr.length; // 数组长度
  const p = arr.slice(); // 用于追溯路径
  let resultLastIndex = result[result.length - 1];
  for (let i = 1; i < len; i++) {
    const arrI = arr[i];
    if (arrI !== 0) {
      resultLastIndex = result[result.length - 1];
      if (arr[resultLastIndex] < arrI) {
        p[i] = resultLastIndex; // 记录前一个索引
        result.push(i);
      } else {
        let left = 0; //开始索引
        let right = result.length - 1; //结束索引
        while (left < right) {
          const middle = ((left + right) / 2) | 0; // 中间索引 向下取整
          if (arr[result[middle]] < arrI) {
            left = middle + 1;
          } else {
            right = middle;
          }
        }

        if (arr[result[left]] > arrI) {
          if (left > 0) {
            p[i] = result[left - 1]; // 记录前一个索引
          }
          result[left] = i;
        }
      }
    }
  }
  let u = result.length; // 结果长度
  let v = result[u - 1]; // 结果最后一个元素
  while (u-- > 0) {
    result[u] = v; // 将结果赋值给结果数组
    v = p[v]; // 将结果的最后一个元素赋值给结果数组
  }
  return result;
}

// console.log(getSequence([2, 6, 7, 8, 9, 11]));
console.log(getSequence([2, 3, 1, 5, 6, 8, 7, 9, 4]));
